package com.ainge.easystudy.binary;

/**
 * 位图算法
 * @author: Ainge
 * @Time: 2021/9/18 12:40
 */
public class MyBitMap {
    /**
     * 每一个word是一个long类型的元素，对应一个64位二进制数据
     */
    private long[] words;

    /**
     * 预期位数的最大值
     * 暂时不支持扩容
     */
    private final int maxBitIndex;


    public MyBitMap(int maxBitIndex){
        this.maxBitIndex = maxBitIndex;
        this.words = new long[getWordIndex(maxBitIndex - 1) + 1];
    }

    public void setBit(int bitIndex){
        if(bitIndex < 0 || bitIndex > maxBitIndex -1){
            throw new IndexOutOfBoundsException();
        }
        // 1L的二进制表示为最右边位只有一个1，为什么左移动 bitIndex位呢？
        // 其实左移动bitIndex位，也相当于移动了(bitIndex % 64)位,因为long有64位,[0,63]位一个周期。
        // 例如此时传入bitIndex = 65值，要设置这个65值对应的状态(1)
        // 64 / 64 = 1,所以它的状态肯定要设置在数组long[1]的long值中
        // 即，取出 long v = long[1] = 00000000...00000000 将第64位也就是第0位设置为1；
        // 此时，long[1] = 00000000...00000001
        // 那么如果再插入一个65值对应的状态的话，此时long[1]=00000000...00000011了
        // 也就是说，如果需要考虑表示海量数据的一个状态，可以考虑使用这种BitMap结构。
        words[getWordIndex(bitIndex)] |= (1L << bitIndex);
    }

    private int getWordIndex(int bitIndex) {
        // 右移6位，相当于除以2的6次方。
        // 为什么要右移6位，也就是说为什么要除以64？
        // 因为long有64位，一个long值，用二进制表示最多能表示64个状态(0或1)
        // 所以long[0]能表示，bitIndex =【0-63】值的状态
        // long[1]能表示[64,127]值的状态
        // 因此，初始化BitMap的时候，如果你知道你要表示的最大值是多少，就意味着你可以确定了数组的大小。
        // 例如，你传入的最大bitIndex = 640，那么意味着640这个值对应的状态，肯定在数组long[10]中，那么这个long[]长度至少为11才行。
        return bitIndex >>> 6;
    }
    public boolean getBit(int bitIndex){
        if(bitIndex < 0 || bitIndex > maxBitIndex -1){
            throw new IndexOutOfBoundsException();
        }
        int wordIndex = getWordIndex(bitIndex);
        return (words[wordIndex] & 1L << bitIndex) != 0;
    }

    public static void main(String[] args) {
        MyBitMap myBitMap = new MyBitMap(3334);
        myBitMap.setBit(1111);
        myBitMap.setBit(2222);

        System.out.println(myBitMap.getBit(1111));
        System.out.println(myBitMap.getBit(2222));
        System.out.println(myBitMap.getBit(3333));


    }

}
